package problem91;

import java.util.PriorityQueue;

//91.解码方法
//https://leetcode.cn/problems/decode-ways/description/
class Solution {
    public int numDecodings(String _s) {
        char[] s = _s.toCharArray();
        if(s[0] == '0') {
            return 0;
        }
        int n = s.length;
        if(n == 1) {
            return 1;
        }

        int[] dp = new int[n];

        //初始化 dp[0] dp[1]
        dp[0] = 1;
        int x = (s[0]-'0') * 10 + s[1]-'0';
        if(x<=26 && x!=10 && x!=20) dp[1] = 2;
        else if(x > 26 && s[1]!='0' || x == 10 || x==20) dp[1] = 1;

        System.out.println(dp[0] + " " + dp[1]);
        for(int i = 2; i<s.length; i++) {
            //s[i]单独解码
            if(s[i] >= '1' && s[i] <='9') {
                dp[i] += dp[i-1];
            }
            //s[i-1]和s[i] 组合解码
            Integer t = Integer.parseInt(_s.substring(i-1, i+1));
            if(t>=10 && t<=26 ) {
                dp[i] += dp[i-2];
            }
            System.out.println(i+" " + dp[i]);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>();

        return dp[n-1];
    }
}

//需要初始化dp[0] , dp[1]
//dp[i]: 到第i个字母有多少种解码方式
// s[i]单独解码 成功: dp[i] += dp[i-1];
// s[i-1]和s[i] 组合解码 成功: dp[i] += dp[i-2];